Shareware Grab Bag/Shareware Grab Bag.iso/090/pkscrypt.arc/PKSCRYPT.DOC

Text File | 1986-03-29 | 13KB | 270 lines

           Public Key System for Encryption and Digital Signatures

                       Copyright (c) Lloyd Miller, 1985
                               Calgary, Alberta



    Public  Key  Encryption  is  a  system  of  encrypting  messages where the
encryption  and  decryption  keys  are  different.  The,  so  called,   public
encryption key, used to encrypt messages is related to the private  decryption
key but it is very difficult to figure out the decyrption key if you only know
the encryption key. (If you think this is confusing, you're right.)

    To send a  secret message to  someone you need  to know only  their public
key. For anyone to send you a  secret message, you need to let them  know your
public key. I have included my public key with these files so that anyone  who
gets this system  can send me  a secret message  (I don't know  why they might
want to but they can). If someone wants me to reply (secretly) then they would
have to send me their public key.

    Messages can  also be  encrypted with  the private  key. This  is called a
signature. Anyone who knows  the public key can  decrypt the message but  only
the person  who knows  the corresponding  private key  could have  created the
message. I have included a message signed by me in this archive that can  only
be decoded with my  public key and thus  could only have been  encrypted by my
private key. Since I havn't given my  private key to anyone and I don't  think
anyone could have figured it out, you  should be able to safely assume that  I
wrote the orginal message.  Signatures are not quite  as useful as the  normal
encryption operation but they do have some very interesting capabilities.

    Messages can be encrypted more than  once. One use for this feature  is to
sign a secret message. To do this  you encrypt the message with both the  your
private key and the recipient's public key. The combination is a message which
only the recipient can read and only you could have created. In order to  read
the message it must be decrypted  twice using the recipeint's private key  and
your public key in the reverse order that it was encrypted.

    The difficulty of  "breaking" the key  is dependant on  the length of  the
keys used. Keys of  8 digits or smaller  are actually quite easy  to break. In
fact you my find  a simple (hee hee)  basic program included with  these files
for "cracking" keys of  5 to 8 digits  (called cracker.bas). I haven't  really
tried it but a key of even 50 digits is estimated that it could be cracked  in
about 4 hours using a super computer and the fastest factoring algoritm known.
A key of  75 digits would  take 104 days  and a key  of 200 digits  would take
3,800,000,000 years. For more on this see the ACM article. If anyone cracks my
75 digit key I would like to hear about it. I suspect you would need a  Cray-2
or equivalent to do it this year.

    The disadvantage of longer keys is that it takes longer to find and create
the key and the encryption/decryption processes are slower as well. A 8  digit
key  will  only  take  about  1/2  minute  to generate with this software on a
standard IBM-PC. A 20 digit key takes  about 90 sec. A 50 digit key,  about 10
min. A 200 digit key will take about 6 to 12 hours. These times may be  longer
or shorter depending on your luck on the random number generator.












    PKSCrypt is a program to perform  the three basic functions reqired for  a
complete public  key encryption  system. The  first question  it asks  is what
function you want to perform, Genkeys, Encrypt, Decrypt, or Quit.

    GENKEYS is the function to generate encryption and decryption keys for the
RSA  (Rivest,  Shamir,   Adleman)  system  of   public  key  encryption.   See
Communications of the ACM, February, 1978.

    GENKEYS takes, as the first input parameter, a single number from 5 to 200
designating the number  of digits desired  in the key.  This number determines
the level of security of the resulting cypher. It also determins the amount of
time needed to generate a key.

    Also input is a name for the  key to be generated. This is an  8 character
filename without extension.

    Output of the function  is two files (besides  all the stuff displayed  on
the screen to keep you from  thinking the software has crashed). The  first is
the public key file called keyname.KEY. It contains two numbers, each of which
contains, at most, the number of digits requested. The first number is  called
"n" and is the product of two large prime numbers (p and q). The second number
is called "e" and is a  number which is relativly prime to  (p-1)*(q-1). These
numbers are the, so called, public key.  This file is the one to be  given out
and/or published for people who want to send you secret messages.

    The second file produced is called keyname.KDY. It also has two numbers in
it. The first is "n" and is the same as the "n" in the public key. The  second
number in this  file is called  "d" and is  the secret decryption  key. "d" is
constructed such that (d * e) MOD ((p -  1) * (q - 1)) = 1. This file  is your
private key for decrypting messages encrypted with your public key and must be
kept secure and private. Perhaps keep it  on a floppy disk and locked up  when
not in use, perhaps with extra copies in separate places.

    The key files are only significant up  to the end of the second number  in
each  file  so  comments  may  be  added  at  the  end  of  the  file. This is
particularily usefull for the public  key files where the name  and/or address
can be added to the  key to indicate the owner  of the key. For an  example of
this, see the file LLOYD.KEY included in this archive. That file is my  public
key and can be used to send me secret messages. When you edit these files make
sure  your  editor  does  not  break  any  long  lines into shorter lines. For
instance a 200 digit key would have  over 200 characters in each of the  first
two lines. These lines must not be broken up into shorter lines.

    The other two functions, ENCRYPT and DECRYPT, use the key files created by
GENKEYS  to  encrypt  and  decrypt  other  files.  The time required for these
functions to do their job depends on  the length of the key used and  the size
of  the  file.  Any  file  can  be  encrypted  with  any key. They can only be
decrypted with the opposite key of the pair.

    ENCRYPT, when selected, will ask for the name of the file to be  encrypted
and the full name of the key file to be used for encryption (ie  "LLOYD.KEY").
Third and last it will ask for a file name to store the encrypted file  under.
ENCRYPT saves the name of the key  file used to encrypt in the output  file in
plain text  so that  the decrypt  system can  easily figure  out which  key is











needed. It does not  store any keys in  the encrypted file, just  the key file
name. Encrypt also saves the input  file name and size in the  encrypted file.
This is so  the decryption can  reproduce the origninal  file. The input  file
name and size  are encrypted so  no extra information  is obtainable from  the
encrypted file without the decryption key.

    DECRYPT first asks for the name of the encrypted file. It reads the header
and offers you the default name for the decryption key. (I.E. if the file  was
encrypted with a key called "test.key" it will ask if you want to decrypt with
"test.kdy".) Normally  you would  anser "yes"  to this  question. If  you have
renamed the key file you want to use  then answer no and type in the name  you
want to use. If you  tell the program the wrong  key to use then nothing  will
work right  after that.  DECRYPT then  decodes the  first part  of the file to
obtain the original file name and  size. Once it has decoded this  information
it will ask you if you want to  use the original name for the decoded file  or
you can enter a new filename. DECRYPT will then procede to decrypt the rest of
the file.


    PKSCrypt can be operated from the command line if you know in advance  the
answers to ALL the questions which will be asked. Just type them following the
command to start up the program. ie:

    pkscrypt genkeys 10 temp quit
    pkscrypt e temp.key temp.dt1 temp.dt2 q
    pkscrypt decrypt temp.dt2 yes yes quit


    Anyone can make as many copies of this software as they want and give them
away so long as the programs and this documentation are included in any copies
and  all  files  are  in  their  original  unmodified  form.  In  fact you are
encouraged to distribute this software  as much as possible by  whatever means
you can  find, electronic,  magnetic, optical  or via  any future technologies
which may be developed. If you find this system usefull then you can encourage
me to write and distribute more of my software by sending $30 to:

        Lloyd Miller
        2420 Capitol Hill Crescent, N.W.
        Calgary, Alberta    T2M-4C2

    If you are a corporate or governmental user then the $30 is not  optional.
If you need an invoice in order to  pay for this please feel free to make  one
out. If you send me a SSAE I will send you a real invoice.

    This software and documentaion is protected by copyright and if you  don't
think that means much then ask a lawyer.

    If you have comments, complaints (heaven forbid) or questions then you can
either send a SASE to the above address or send a message to me (Lloyd Miller)
via Fidonet(TM of Tom Jennings) node 134/1, "The Calgary Fido". If you want to
send  encrypted  messages  via  Fidonet  then  you  will need your sysop's co-
operation to send "attached files". Your  sysop will not be able to  read your
secret messages. If you want  to send encrypted messages via  traditional mail
then you would have to send floppy disks.












    This software is designed to run on an IBM-PC using MS-DOS version 2.00 or
later.  I  have  tried  to  avoid  using  any features of the IBM-PC which are
machine dependant so I believe it should work on any system which uses  MS-DOS
or PC-DOS but it has not been  tested on many other types of systems.  I would
like to hear from  you if you have  tried it on any  other systems and if  you
have had any  probelms or not.  I have tested  the system on  a Sanyo MBC  555
(with a V-20 CPU chip) and it works fine.

    These  programs  are  written  in  Modula-2 using the Logitech Modula-2/86
compiler system. I would be willing to consider converting these programs  for
use  with  other  Modula-2  systems  if  anyone  wants  to  pay  me  to do the
convertion. I would not consider converting the programs to another  language.
The nature of these programs  would probably eliminate from consideration  any
M-CODE or P-CODE  interpreter style compiler  systems since they  would become
prohibitivly slow.


    Version History

        Version 0.0     Distributed as three  programs, GENKEYS, ENCRYPT,  and
DECRYPT. Worked fine

        Version 0.01    Combined  the  three  programs  into  one  executable,
PKSCRYPT, to save space on my disk. The same key files and encrypted files are
used.

        Version 0.01a   Update to Version 2.0  of the compiler. Some  spelling
corrections.

        Version 0.01b   Eliminated  last  few  remaining  REALS.  Added  a few
"Please  Wait"  messages.  Documented  the  command  line  operation which has
allways been available.

        Version 0.01c   Converted a few selected routines to mahine code.  Not
much speed difference resulted. Hardly worth the effort.

        Version 0.01d   Allows   smaller   keys   (5   digits)   and  includes
cracker.bas for breaking keys of 8 digits and smaller.

        Version 0.02    Changed the  long arithmetic  from byte  at a  time to
word at a time.  Very nice speed improvement.  Generated a 200 digit  key in 4
hours  40  min.  Minimum  key  size  increased  back up to 7 digits because of
occational hangs on smaller keys.
    Sample decrypt times for 10 byte message on regular 8088 at 4.77mhz.

        Key digits      V0.01d          V0.02

         10              0:12            0:12
         20              0:20            0:15
         30              0:31            0:15
         40              1:02            0:26
         50              1:42            0:38
        200             36:57           10:29

        Version 0.02a   Found another bug in the long arithmetic. V0.02  would











occationally  dump  with  a  divide  by  zero. Some more speed-up implememted,
relativly minor.

                                                                  Lloyd Miller
                                                                 1986 March 29